home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / intrvews / xgrab.lha / xgrab / grabst / levels.c < prev    next >
C/C++ Source or Header  |  1990-03-06  |  10KB  |  368 lines
  1. /**
  2.    GRAB Graph Layout and Browser System
  3.  
  4.    Copyright (c) 1986, 1988 Regents of the University of California
  5.    Copyright (c) 1989, Tera Computer Company
  6.  **/
  7.  
  8.   /* levels.c -- routines to manipulate the level structure of the digraph */
  9.  
  10. #include "malloc.h"
  11. #include <string.h>
  12.  
  13. #include "attribute.h"
  14. #include "digraph.h"
  15. #include "debug.h"
  16.  
  17. #define DUMMY_SHAPE    POINT        /* default shape for dummy */
  18. #define    DUMMY_BRUSH    SOLIDB        /* default brush for dummy */
  19. #define    DUMMY_COLOR    BLACK        /* default color for dummy */
  20.  
  21. VERTEX *insert_vertex();
  22. NODE *insert_node();
  23. LEVEL *find_level();
  24. char **dispose_out_edge();
  25.  
  26. add_level(digraph, members)
  27. DIGRAPH *digraph;
  28. SET *members;     /* members of the level */
  29.   /* add_level adds a new level to digraph with the vertices in members. */
  30. {
  31.     VNO vno;        /* each vertex number */
  32.     LEVEL *level;   /* the new level */
  33.  
  34.     new(level, LEVEL);
  35.     Prev_level(level) = NULL;
  36.     Next_level(level) = digraph->levels;   /* link in at the head */
  37.     digraph->levels = level;
  38.  
  39.     if (Next_level(level) != NULL)         /* fix previous of next */
  40.     {
  41.         Prev_level(Next_level(level)) = level;
  42.     }
  43.     else                                   /* this is the last level */
  44.     {
  45.         Last_level(digraph) = level;
  46.     }
  47.  
  48.     Order(level) = NULL;
  49.     Lno(level) = 0;    /* don't know level number yet */
  50.     Num_cross(level) = -1;          /* no crossings calculated yet */    
  51.     init_set(Members(level));
  52.  
  53.     each_element(members, vno)
  54.     loop
  55.           /* add a non-dummy member */
  56.         add_member(digraph, level, vno, NORMAL);
  57.     endloop
  58. } /* add_level */
  59.  
  60. add_dummy(digraph, new_level, vno, ante_set) 
  61. DIGRAPH *digraph;
  62. LEVEL *new_level;      /* level to put the dummy on */
  63. VNO vno;               /* succedent of the dummy */
  64. SET *ante_set;         /* antecedents of the dummy */
  65.   /**
  66.      add_dummy adds dummy nodes to new_level with succedent vno and antecedents
  67.      in ante_set.  If vno has no succedents, then vno itself is moved from its 
  68.      current level to new_level instead of creating dummies.
  69.    **/
  70. {
  71.     char name[100];        /* name of the dummy */
  72.     NODE *dummy_node;
  73.     VERTEX *dummy_vertex;
  74.     VNO dummy_vno;         /* the dummy vno */
  75.     VNO from_vno;          /* each antecedent of dummy */
  76.     int sub_num;      /* counter for more than one dummy */
  77.     int i;
  78.     char **attr;
  79.  
  80.     if (empty(Succ_set(Node(digraph, vno))) &&
  81.         equal(Ante_set(Node(digraph, vno)), ante_set))
  82.     {
  83.         LEVEL *vno_level;      /* level vno is on */
  84.  
  85.           /* move to new_level */
  86.         vno_level = find_level(digraph, vno);    /* get vno's level */
  87.         move_member(digraph, vno_level, vno, new_level);
  88.         return;
  89.     }
  90.  
  91.       /* otherwise create a dummy */
  92.     Last_dummy(Member(digraph, vno))++;   /* adding another dummy */
  93.     sub_num = 0;              /* for more than one dummy */
  94.  
  95.     each_element(ante_set, from_vno)      /* fix up antecedents */
  96.     loop
  97.         sprintf(name, "->%s.%d.%d", Name(Node(digraph, vno)), 
  98.             Last_dummy(Member(digraph, vno)), sub_num++);
  99.  
  100.           /* create the array of (null) attributes */
  101.         attr = (char **) malloc(NNodeAttr(digraph) * sizeof(char *));
  102.  
  103.         for (i = 0; i < NNodeAttr(digraph); i++)
  104.         {
  105.             strsave(attr[i], NULL_STRING);
  106.         }
  107.  
  108.           /* create a dummy. */
  109.         dummy_vertex = insert_vertex(digraph, name);
  110.         dummy_node = insert_node(digraph, dummy_vertex, attr, DUMMY_SHAPE,
  111.                            DUMMY_BRUSH, DUMMY_COLOR, TRUE, 0, 0, DUMMY);
  112.       /**
  113.          for multi-graph and two-way edges:  All edges between a pair
  114.          of nodes follow the same path, including dummy nodes.  So
  115.          dummy nodes are made wider to support more than one distinct 
  116.          in and out edge.
  117.        **/
  118.     Half_width(dummy_node) += EDGE_GAP * 
  119.                     max_edges(Node(digraph, from_vno),
  120.                           Node(digraph, vno)) / 2;
  121.         dummy_vno = Vno(dummy_node);
  122.  
  123.         remove_element(Succ_set(Node(digraph, from_vno)), vno);
  124.         add_element(Succ_set(Node(digraph, from_vno)), dummy_vno);
  125.  
  126.         add_element(Ante_set(Node(digraph, dummy_vno)), from_vno);
  127.         add_element(Succ_set(Node(digraph, dummy_vno)), vno);
  128.  
  129.         remove_element(Ante_set(Node(digraph, vno)), from_vno);  
  130.                             /* shorten span */
  131.         add_element(Ante_set(Node(digraph, vno)), dummy_vno);
  132.  
  133.           /* now add a dummy member */
  134.         add_member(digraph, new_level, dummy_vno, DUMMY); 
  135.  
  136.         if (debug)
  137.         {
  138.         printf("\nadd_dummy:  created dummy '%s'\n", 
  139.            Name(Node(digraph, dummy_vno)));
  140.         printf("   Succedents: ");
  141.         print_set(digraph, Succ_set(Node(digraph, dummy_vno)));
  142.         printf("\n   Antecedents: ");
  143.         print_set(digraph, Ante_set(Node(digraph, dummy_vno)));
  144.         printf("\n");
  145.         }
  146.     endloop
  147. } /* add_dummy */
  148.  
  149. add_member(digraph, level, vno, status)    
  150. DIGRAPH *digraph;
  151. LEVEL *level;     /* level for new member */
  152. VNO vno;          /* vno of new member */
  153. STATUS status;    /* status of new member */
  154.   /* add_member adds a new member to level. */
  155. {
  156.     MEMBER *member;    /* the new member */
  157.  
  158.     member = Member(digraph, vno);
  159.     Next_member(member) = Order(level);
  160.     Order(level) = member;
  161.     Prev_member(member) = NULL;
  162.  
  163.     if (Next_member(member) != NULL)
  164.     {
  165.         Prev_member(Next_member(member)) = member;
  166.     }
  167.  
  168.     Status(member) = status;
  169.     Bc(member, UP) = Bc(member, DOWN) = NO_BC;
  170.     Level_no(member) = Lno(level); 
  171.     add_element(Members(level), vno);
  172. } /* add_member */
  173.  
  174. remove_member(digraph, level, vno)    
  175. DIGRAPH *digraph;
  176. LEVEL *level;
  177. VNO vno;
  178.   /**
  179.      remove_member removes the member for vno from level.  If vno is not
  180.      a member of level, an error occurs.
  181.    **/
  182. { 
  183.     MEMBER *member;
  184.  
  185.     member = Member(digraph, vno);
  186.  
  187.     if (Prev_member(member) == NULL)            /* new head */
  188.     {
  189.         Order(level) = Next_member(member);
  190.     }
  191.     else 
  192.     {
  193.         Next_member(Prev_member(member)) = Next_member(member);
  194.     }
  195.  
  196.     if (Next_member(member) != NULL)
  197.     {
  198.         Prev_member(Next_member(member)) = Prev_member(member);
  199.     }
  200.  
  201.     Next_member(member) = Prev_member(member) = NULL;
  202.     remove_element(Members(level), vno);
  203. } /* remove_member */
  204.  
  205. move_member(digraph, from_level, vno, to_level)    
  206. DIGRAPH *digraph;
  207. LEVEL *from_level;
  208. VNO vno;
  209. LEVEL *to_level;
  210.   /* move_member moves vno from from_level to to_level. */
  211. {
  212.     MEMBER *member;
  213.  
  214.     member = Member(digraph, vno);
  215.     remove_member(digraph, from_level, vno);    /* remove from previous level */
  216.     add_member(digraph, to_level, vno, Status(member));
  217. } /* move_member */
  218.  
  219. LEVEL *find_level(digraph, vno)
  220. DIGRAPH *digraph;
  221. VNO vno;
  222.   /**
  223.      find_level finds the level in which vno is a member in digraph.  If there
  224.      is no such level, NULL is returned.
  225.    **/
  226. {
  227.     LEVEL *level;  /* each level */
  228.  
  229.     if (debug)
  230.     {
  231.         printf("\nfind_level:  looking for level of '%s'\n", 
  232.            Name(Node(digraph, vno)));
  233.     }
  234.  
  235.     each_level(digraph, level)
  236.     loop
  237.         if (in(Members(level), vno))
  238.         {
  239.           return(level);
  240.     }
  241.     endloop
  242.     return(NULL);
  243. } /* find_level */
  244.  
  245. remove_long_spans(digraph)
  246. DIGRAPH *digraph;
  247.   /**
  248.      remove_long_spans follows dummy edges from NORMAL node to NORMAL node and
  249.      removes the long span from the appropriate successor and ancestor sets. 
  250.    **/
  251. {
  252.     NODE *node, *next;
  253.     VNO vno;
  254.     NODE *next_dummy();
  255.  
  256.     each_node(digraph, node)
  257.     loop
  258.         if (Status(node) != NORMAL)
  259.     {
  260.             continue;
  261.     }
  262.  
  263.     each_element(Succ_set(node), vno)
  264.     loop
  265.         next = Node(digraph, vno);
  266.  
  267.         if (!Is_dummy(next))
  268.         {
  269.         continue;
  270.         }
  271.  
  272.         while (Is_dummy(next))
  273.         {
  274.         next = next_dummy(digraph, next);
  275.         }
  276.  
  277.         if (Status(next) != NORMAL)
  278.         {
  279.         continue;
  280.         }
  281.  
  282.           /**
  283.          next is now the next NORMAL node after a series
  284.              of dummy nodes
  285.            **/
  286.         remove_element(Succ_set(node), Vno(next));
  287.         remove_element(Ante_set(next), Vno(node));
  288.     endloop
  289.     endloop
  290. } /* remove_long_spans */
  291.  
  292. OUTEDGE *get_edge();
  293. INEDGE *get_in_edge();
  294.  
  295. reverse_edge(digraph, vno, root_vno, ord)
  296. DIGRAPH *digraph;
  297. VNO vno;        /* last vno before cycle */
  298. VNO root_vno;        /* vertex # of successor to vno, causing cycle */
  299. int ord;        /* ordinality of the edge */
  300.   /**
  301.      reverse-edge removes an edge and its associated set members, and adds
  302.      a new edge, with the same attributes, going in the opposite direction.
  303.    **/
  304. {
  305.     NODE *node, *root_node;
  306.     int errval;            /* 0 if insert_edge successful */
  307.     NODE *realnode, *realroot;
  308.     int realord;
  309.     INEDGE *inedge;
  310.     OUTEDGE *outedge;
  311.     BRUSH brush;
  312.     COLOR color;
  313.     char **attr;
  314.     BOOL reverse;
  315.  
  316.     node = Node(digraph, vno);
  317.     root_node = Node(digraph, root_vno);
  318.  
  319.     if (Is_dummy(node) || Is_dummy(root_node))
  320.     {
  321.     return;
  322.     }
  323.     
  324.     outedge = get_edge(digraph, node, root_node, ord);
  325.     inedge = get_in_edge(digraph, node, root_node, ord);
  326.       /**
  327.      nodes could be coalescers, so we need to get the real 
  328.      endpoints of the edge.
  329.        **/
  330.     realroot = Node(digraph, To_vno(outedge));
  331.     realnode = Node(digraph, From_vno(inedge));
  332.     reverse = !Edge_reversed(outedge);
  333.     realord = Ord(outedge);
  334.  
  335.     if (debug)
  336.     {
  337.     printf("Reversing Edge: (%s, %s)\n", Name(node), Name(root_node));
  338.     }
  339.  
  340.       /**
  341.      note: normally, you'd have to check if this were the last edge
  342.      between the two nodes before you removed the link.  But we know 
  343.      that all edges between two nodes go in the same direction, so if 
  344.      we're reversing this edge, we're reversing all the edges from node 
  345.      to root_node, and we can safely remove the link.
  346.        **/
  347.     remove_link(node, root_node);
  348.     attr = dispose_out_edge(realnode, Vno(realroot), realord, &brush, 
  349.                 &color);
  350.     dispose_in_edge(realroot, Vno(realnode), realord);
  351.     errval = insert_edge(digraph, Vno(realroot), Vno(realnode), attr, brush, 
  352.              color);
  353.     realord = max_edges(realroot, realnode);
  354.       /* ord has now changed */
  355.  
  356.     if (errval != 0) 
  357.     {
  358.     PrintError("reverse_edge: illegal vertex number");
  359.     } 
  360.     else 
  361.     {    
  362.     outedge = get_edge(digraph, realroot, realnode, realord);
  363.     inedge = get_in_edge(digraph, realroot, realnode, realord);
  364.     Edge_reversed(outedge) = reverse;
  365.     Edge_reversed(inedge) = reverse;
  366.     }
  367. }  /* reverse_edge */
  368.